package com.example.leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。
 * 下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
 * <p>
 * <p>
 * 输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面，用户得到的输入只有一个子树根节点
 */
public class Tree6 {
    public static void main(String[] args) {

    }


    List<TreeLinkNode> middleTree = new ArrayList<>();

    /**
     * 看不懂题目？入参给的只是一棵子树
     *
     * @param pNode
     * @return
     */
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 获取根节点（从目标节点通过next不断回溯）
        TreeLinkNode root = pNode;
        while (root.next != null) {
            root = root.next;
        }

        // 中序遍历获取所有元素(将所有元素放到集合中)
        middleOrder(root);

        //middleTree.size() -1；防止middleTree.get(i + 1)数组越界
        for (int i = 0; i < middleTree.size() - 1; i++) {
            TreeLinkNode treeLinkNode = middleTree.get(i);
            if (treeLinkNode.val == pNode.val) {
                return middleTree.get(i + 1);
            }
        }

        return null;
    }

    private void middleOrder(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        // 左
        middleOrder(root.left);
        // 中
        middleTree.add(root);
        // 右
        middleOrder(root.right);
    }
}
